package algorithm.leetcode.medium;

/*
 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。
 每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。
 每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/28
 */
public class Question289 {

    public static void main(String[] args) {

    }

    /**
     * 思路： 基于标记-更新
     * 1——保持1
     * -1——1转0
     * 0——保持0
     * -2——0转1
     */
    public void gameOfLife(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = checkLoc(board, i, j);
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = board[i][j] == 1 || board[i][j] == -2 ? 1 : 0;
            }
        }
    }

    /**
     * 存活 周围有3或者4个存活还是存活 不是存活但是周围有3个存活的时候标记存活
     */
    private int checkLoc(int[][] board, int i, int j) {
        int count = 0;
        int left = Math.max(j - 1, 0);
        int right = Math.min(j + 1, board[i].length - 1);
        int top = Math.max(i - 1, 0);
        int bottom = Math.min(i + 1, board.length - 1);
        for (int x = top; x <= bottom; x++) {
            for (int y = left; y <= right; y++) {
                // 这样可以算 8个位置
                count = board[x][y] == 1 || board[x][y] == -1 ? count + 1 : count;
            }
        }
        // 存活 周围有3或者4个存活还是存活 不是存活但是周围有3个存活的时候标记存活
        return board[i][j] == 1 ? (count == 3 || count == 4 ? 1 : -1) : (count == 3 ? -2 : 0);
    }
}
